class Disjoinset{
public:
    vector<int> parent,rank;

    Disjoinset(int n):parent(n),rank(n,0){
        for(int i=0;i<n;i++){
            parent[i]=i;
        }
    }

    int find(int x){
        if(parent[x] != x){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void merge(int x, int y){
        int rootx = find(x);
        int rooty = find(y);
        if(rootx != rooty){
            if(rank[rootx] < rank[rooty]){
                swap(rootx,rooty);
            }
            parent[rooty] = rootx;
            if(rank[rootx]==rank[rooty]){
                rank[rootx]+=1;
            }
        }
    }
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty())    return 0;
        int x = grid.size();
        int y = grid[0].size();

        Disjoinset ds(x*y);
        unordered_map<int,pair<int,int>> id;

        for(int i=0;i<x;i++){
            for(int j=0;j<y;j++){
                if(grid[i][j]=='1'){
                    int index = i*y+j;
                    id[index]={i,j};

                    if(j>0 && grid[i][j-1]=='1'){
                        int leftindex = i*y+j-1;
                        ds.merge(index,leftindex);
                    }

                    if(i>0 && grid[i-1][j]=='1'){
                        int topindex = (i-1)*y+j;
                        ds.merge(index,topindex);
                    }
                }
            }
        }

        int res = 0;
        for(const auto& d:id){
            int index = d.first;
            if(index==ds.find(index)){
                res++;
            }
        }
        return res;
    }
};
